package com.zjw.algorithm;


import java.util.Arrays;
import java.util.Comparator;

/**
 * 给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTimei, endTimei, valuei] 。第 i 个活动开始于 startTimei ，结束于 endTimei ，如果你参加这个活动，那么你可以得到价值 valuei 。你 最多 可以参加 两个时间不重叠 活动，使得它们的价值之和 最大 。
 * <p>
 * 请你返回价值之和的 最大值 。
 * <p>
 * 注意，活动的开始时间和结束时间是 包括 在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为 t ，那么下一个活动必须在 t + 1 或之后的时间开始。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/two-best-non-overlapping-events
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 输入：events = [[1,3,2],[4,5,2],[2,4,3]]
 * 输出：4
 * 解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。
 * <p>
 * <p>
 * 输入：events = [[1,3,2],[4,5,2],[1,5,5]]
 * 输出：5
 * 解释：选择活动 2 ，价值和为 5 。
 * <p>
 * <p>
 * 输入：events = [[1,5,3],[1,5,1],[6,6,5]]
 * 输出：8
 * 解释：选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。
 */
public class Solution4_2 {

    public static void main(String[] args) {
        System.out.println(new Solution4_2().maxTwoEvents(new int[][]{{1, 3, 2}, {4, 5, 2}, {2, 4, 3}}));
        System.out.println(new Solution4_2().maxTwoEvents(new int[][]{{1, 3, 2}, {4, 5, 2}, {1, 5, 5}}));
        System.out.println(new Solution4_2().maxTwoEvents(new int[][]{{1, 5, 3}, {1, 5, 1}, {6, 6, 5}}));


        System.out.println(new Solution4_2().maxTwoEvents2(new int[][]{{1, 3, 2}, {4, 5, 2}, {2, 4, 3}}));
        System.out.println(new Solution4_2().maxTwoEvents2(new int[][]{{1, 3, 2}, {4, 5, 2}, {1, 5, 5}}));
        System.out.println(new Solution4_2().maxTwoEvents2(new int[][]{{1, 5, 3}, {1, 5, 1}, {6, 6, 5}}));
    }

    /**
     * 先用暴力法
     */
    public int maxTwoEvents(int[][] events) {
        int currentValue = 0;

        for (int i = 0; i < events.length; ++i) {
            int value = findMaxValue(events, i);
            currentValue = Math.max(currentValue, value);
        }

        return currentValue;
    }

    //寻找[0,end)与end所组成的最大值
    private int findMaxValue(int[][] events, int end) {
        if (end == 0) {
            return events[0][2];
        }

        int value = events[end][2];
        int endEventStart = events[end][0];
        int endEventEnd = events[end][1];

        for (int i = 0; i < end; i++) {
            int[] event = events[i];
            if ((event[0] < endEventStart && event[1] < endEventStart) || (event[0] > endEventEnd && event[1] > endEventEnd)) {
                value = Math.max(value, events[end][2] + event[2]);
            }

        }

        return value;
    }


    /**
     * NlogN
     * */
    public int maxTwoEvents2(int[][] events) {
        if (events.length == 0) {
            return 0;
        }
        //根据开始时间升序排
        Arrays.sort(events, Comparator.comparingInt(o -> o[0]));

        //从i开始参加活动其中的一个最大价值
        int[] dp = new int[events.length];
        dp[events.length - 1] = events[events.length - 1][2];
        for (int i = events.length - 2; i >= 0; i--) {
            dp[i] = Math.max(dp[i + 1], events[i][2]);
        }

        int maxValue = 0;
        for (int i = 0; i < events.length; i++) {
            int endTime = events[i][1];
            int value = events[i][2];

            int pl = i + 1;
            int pr = events.length - 1;
            int middle;
            while (pl < pr) {
                middle = (pl + pr) >> 1;

                if (events[middle][0] > endTime) {
                    pr = middle;
                } else {
                    pl = middle + 1;
                }
            }
            //check
            if (events[pr][0] > endTime) {
                maxValue = Math.max(maxValue, value + dp[pr]);
            } else {
                maxValue = Math.max(maxValue, value);
            }

        }
        return maxValue;
    }

}
